//
//  08_06_汉诺塔问题.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/3.
//

import UIKit
/**
 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
 (1) 每次只能移动一个盘子;
 (2) 盘子只能从柱子顶端滑出移到下一根柱子;
 (3) 盘子只能叠在比它大的盘子上。
 你需要原地修改栈。
 示例1:

  输入：A = [2, 1, 0], B = [], C = []
  输出：C = [2, 1, 0]
 示例2:

  输入：A = [1, 0], B = [], C = []
  输出：C = [1, 0]
 提示:

 A中盘子的数目不大于14个。
 
 */
class HanNuoTa: NSObject {
    func hanota(_ A: inout [Int], _ B: inout [Int], _ C: inout [Int]) {
        move(A.count, &A, &B, &C)
    }
    
    func move(_ size: Int, _ start: inout [Int], _ auxiliary: inout [Int], _ target: inout [Int] ) {
        if size == 1 {
            target.append(start.removeLast())
            return
        }
        //首先将 n-1 个盘子，从第一个柱子移动到第二个柱子
        move(size - 1, &start, &target,  &auxiliary)
        //然后将最后一个盘子移动到第三个柱子上
        let max = start.removeLast()
        target.append(max)
        //最后将第二个柱子上的 n-1 个盘子，移动到第三个柱子上
        move(size - 1,  &auxiliary, &start, &target)

    }
}
